package LinkedList.Medium;

import java.util.List;

public class LC0160 {
    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode(int[] vals) {
            val = vals[0];
            next = null;
            ListNode ptr = this;
            for (int i = 1; i < vals.length; i++) {
                ptr.next = new ListNode(vals[i]);
                ptr = ptr.next;
            }
        }

        ListNode(int[] vals, ListNode anotherList) {
            val = vals[0];
            next = anotherList;
            ListNode ptr = this;
            for (int i = 1; i < vals.length; i++) {
                ptr.next = new ListNode(vals[i]);
                ptr = ptr.next;
                ptr.next = anotherList;
            }
        }
    }

    /**
     * Krahets@LeetCode的解法。这种解法的关键之处在于消除两个链表之间的长度差。使用两个指针分别指向两个链表，并在一个链表遍历完时切换到另一个，
     * 如此一来，两个指针便会在某个时刻相遇，并且这个相遇的位置就是交点的位置。
     * 这是容易证明的。我们不考虑特殊情况，假设两个链表充分长，并且交点前后各有一段充分长的子链表。链表A在交点前的子链表的长度为a，
     * 链表B在交点前的子链表的长度为b，公共链表的长度为c，那么当两个指针相遇时，指针经过的距离为a+(b-c)=b+(a-c)。
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ptrA = headA, ptrB = headB;
        while (ptrA != ptrB) {
            if (ptrA == null) ptrA = headB;
            else ptrA = ptrA.next;
            if (ptrB == null) ptrB = headA;
            else ptrB = ptrB.next;
        }
        if (ptrA == null) return null;
        else return ptrA;
    }

    public static void main(String[] args) {
        ListNode headA = new ListNode(new int[]{
                3});
        ListNode headB = new ListNode(new int[]{
                2}, headA);
        ListNode intersectionNode = getIntersectionNode(headA, headB);
    }
}
